"""
给定一个没有重复数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
'''思想就是：将每个数与第p个做交换 把后面的做全排列，直到p==q'''
"""

import time
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        begin = time.clock()
        self.res = []
        def perm(n, p, q):
            if p == q:
                self.res.append(n[:])
            else:
                for i in range(p, q+1):
                    n[i], n[p] = n[p], n[i]
                    perm(n, p+1, q)
                    n[i], n[p] = n[p], n[i]
        perm(nums, 0, len(nums) - 1)
        end = time.clock()
        print("0",end-begin)
        return self.res

    def permute_1(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        begin = time.clock()
        if len(nums) <= 1:
            return [nums]
        self.res = []
        def perm(nums, cur):
            if len(nums) <= 2:
                self.res.append(cur+nums)
                self.res.append(cur+nums[::-1])
            else:
                for i, x in enumerate(nums):
                    perm(nums[:i]+nums[i+1:], cur+[x])
        perm(nums,[])
        end = time.clock()
        print("1",end-begin)
        return self.res

s = Solution()
s.permute([i for i in range(10)])
s.permute_1([i for i in range(10)])